package com.gitee.wsl.compose.chart.geometry.model.pool

/*
 * Copyright 2014 Hannes Janetzek
 *
 * This file is part of the OpenScienceMap project (http://www.opensciencemap.org).
 *
 * This program is free software: you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 */
/**
 * Stripped down HashMap making HashItem entries public - So you have your custom
 * 'Entry' holding key and value. HashItem must implement equals() and hashCode()
 * only for the 'key' part. Items may only be in one KeyMap at a time!
 *
 * KeyMap.put(HashItem, boolean replace) allows to get or add an item in one invocation.
 *
 * TODO add to NOTICE file
 * The VTM library includes software developed as part of the Apache
 * Harmony project which is copyright 2006, The Apache Software Foundation and
 * released under the Apache License 2.0. http://harmony.apache.org
 */
/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements. See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License. You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

import kotlin.jvm.JvmOverloads
import kotlin.math.max

/**
 *
 *
 * Note: the implementation of `KeyMap` is not synchronized. If one thread
 * of several threads accessing an instance modifies the map structurally,
 * access to the map needs to be synchronized. A structural modification is an
 * operation that adds or removes an entry. Changes in the value of an entry are
 * not structural changes.
 *
 * @param <K> the type of keys maintained by this map
</K> */
class KeyMap<K : KeyMap.HashItem>(capacity: Int, loadFactor: Float = 0f) : Inlist<KeyMap<K>>() {

    /**
     * The hash table. If this hash map contains a mapping for null, it is
     * not represented this hash table.
     */
    var table: Array<HashItem?> = EMPTY_TABLE

    /**
     * The number of mappings in this hash map.
     */
    var size = 0

    /**
     * The table is rehashed when its size exceeds this threshold.
     * The value of this field is generally .75 * capacity, except when
     * the capacity is zero, as described in the EMPTY_TABLE declaration
     * above.
     */
    private var threshold = 0

    /**
     * Constructs a new empty `HashMap` instance.
     */
    /*constructor() {
        table = EMPTY_TABLE
        threshold = -1 // Forces first put invocation to replace EMPTY_TABLE
    }*/

    init {
        require(capacity >= 0) { "Capacity: $capacity" }
        var capacity = capacity
        if (capacity == 0) {
            table = EMPTY_TABLE
            threshold = -1 // Forces first put() to replace EMPTY_TABLE
        }else{
            capacity = if (capacity < MINIMUM_CAPACITY) {
                MINIMUM_CAPACITY
            } else if (capacity > MAXIMUM_CAPACITY) {
                MAXIMUM_CAPACITY
            } else {
                roundUpToPowerOfTwo(capacity)
            }
            makeTable(capacity)
        }

    }

    /**
     * Constructs a new `HashMap` instance with the specified capacity.
     *
     * @param capacity
     * the initial capacity of this hash map.
     * @throws IllegalArgumentException
     * when the capacity is less than zero.
     */
    /*constructor(capacity: Int) {
        var capacity = capacity
        require(!(capacity < 0)) { "Capacity: $capacity" }
        if (capacity == 0) {
            table = EMPTY_TABLE
            threshold = -1 // Forces first put() to replace EMPTY_TABLE
            return
        }
        capacity = if (capacity < MINIMUM_CAPACITY) {
            MINIMUM_CAPACITY
        } else if (capacity > MAXIMUM_CAPACITY) {
            MAXIMUM_CAPACITY
        } else {
            roundUpToPowerOfTwo(capacity)
        }
        makeTable(capacity)
    }*/

    /**
     * Constructs a new `HashMap` instance with the specified capacity and
     * load factor.
     *
     * @param capacity
     * the initial capacity of this hash map.
     * @param loadFactor
     * the initial load factor.
     * @throws IllegalArgumentException
     * when the capacity is less than zero or the load factor is
     * less or equal to zero or NaN.
     */
   /* constructor(capacity: Int, loadFactor: Float) : this(capacity) {
        if (loadFactor <= 0 || java.lang.Float.isNaN(loadFactor)) {
            throw IllegalArgumentException("Load factor: $loadFactor")
        }

        *//* Note that this implementation ignores loadFactor; it always uses
		 * a load factor of 3/4. This simplifies the code and generally
		 * improves performance. *//*
    }*/

    /**
     * This method is called from the pseudo-constructors (clone and readObject)
     * prior to invoking constructorPut/constructorPutAll, which invoke the
     * overridden constructorNewEntry method. Normally it is a VERY bad idea to
     * invoke an overridden method from a pseudo-constructor (Effective Java
     * Item 17). In this case it is unavoidable, and the init method provides a
     * workaround.
     */
    //fun init() {}
    val isEmpty: Boolean
        /**
         * Returns whether this map is empty.
         *
         * @return `true` if this map has no elements, `false`
         * otherwise.
         * @see .size
         */
        get() = size == 0

    /**
     * Returns the number of elements in this map.
     *
     * @return the number of elements in this map.
     */
    fun size(): Int {
        return size
    }

    /**
     * Returns the value of the mapping with the specified key.
     *
     * @param key
     * the key.
     * @return the value of the mapping with the specified key, or `null`
     * if no mapping for the specified key is found.
     */
    operator fun get(key: HashItem): K? {

        // Doug Lea's supplemental secondaryHash function (inlined)
        var hash = key.hashCode()
        hash = hash xor (hash ushr 20 xor (hash ushr 12))
        hash = hash xor (hash ushr 7 xor (hash ushr 4))
        val tab = table
        var e = tab[hash and (tab.size - 1)]
        while (e != null) {
            val eKey: HashItem = e
            if (eKey == key || e.hash == hash && key == eKey) {
                return eKey as K
            }
            e = e.next
        }
        return null
    }

    /**
     * Maps the specified key to the specified value.
     *
     * @param key
     * the key.
     * @param value
     * the value.
     * @return the value of any previous mapping with the specified key or
     * `null` if there was no such mapping.
     */
    @JvmOverloads
    fun put(key: K, replace: Boolean = true): K? {
        if (key.next != null) throw IllegalStateException("item not unhooked")
        val hash = secondaryHash(key.hashCode())
        var tab = table
        var index = hash and tab.size - 1
        var e = tab[index]
        while (e != null) {
            if (e.hash == hash && key == e) {
                if (replace) {
                    tab[index] = remove(tab[index] as K, e)
                    tab[index] = push(tab[index] as K, key)
                }
                //V oldValue = e.value;
                //e.value = value;
                return e as K //oldValue;
            }
            e = e.next
        }

        // No entry key is present; create one
        if (size++ > threshold) {
            tab = doubleCapacity()
            index = hash and tab.size - 1
        }
        addNewEntry(key, hash, index)
        return null
    }

    /**
     * Removes the mapping with the specified key from this map.
     *
     * @param key
     * the key of the mapping to remove.
     * @return the value of the removed mapping or `null` if no mapping
     * for the specified key was found.
     */
    fun remove(key: K): K? {
        val hash = secondaryHash(key.hashCode())
        val tab = table
        val index = hash and tab.size - 1
        var e = tab[index]
        var prev: HashItem? = null
        while (e != null) {
            if (e.hash == hash && key.equals(e)) {
                if (prev == null) {
                    tab[index] = e.next
                } else {
                    prev.next = e.next
                }
                e.next = null
                //modCount++;
                size--
                //postRemove(e);
                return e as K
            }
            prev = e
            e = e.next
        }
        return null
    }

    /**
     * Creates a new entry for the given key, value, hash, and index and
     * inserts it into the hash table. This method is called by put
     * (and indirectly, putAll), and overridden by LinkedHashMap. The hash
     * must incorporate the secondary hash function.
     */
    fun addNewEntry(key: K, hash: Int, index: Int) {
        key.setIndex(hash, table[index])
        table[index] = key
    }

    /**
     * Allocate a table of the given capacity and set the threshold accordingly.
     *
     * @param newCapacity must be a power of two
     */
    private fun makeTable(newCapacity: Int): Array<HashItem?> {
        val newTable = arrayOfNulls<HashItem>(newCapacity)
        table = newTable
        threshold = (newCapacity shr 1) + (newCapacity shr 2) // 3/4 capacity
        return newTable
    }

    /**
     * Doubles the capacity of the hash table. Existing entries are placed in
     * the correct bucket on the enlarged table. If the current capacity is,
     * MAXIMUM_CAPACITY, this method is a no-op. Returns the table, which
     * will be new unless we were already at MAXIMUM_CAPACITY.
     */
    private fun doubleCapacity(): Array<HashItem?> {
        val oldTable = table
        val oldCapacity = oldTable.size
        if (oldCapacity == MAXIMUM_CAPACITY) {
            return oldTable
        }
        val newCapacity = oldCapacity * 2
        val newTable = makeTable(newCapacity)
        if (size == 0) {
            return newTable
        }
        for (j in 0 until oldCapacity) {
            /* Rehash the bucket using the minimum number of field writes.
			 * This is the most subtle and delicate code in the class. */
            var e = oldTable.get(j) ?: continue
            var highBit = e.hash and oldCapacity
            var broken: HashItem? = null
            newTable[j or highBit] = e
            var n = e.next
            while (n != null) {
                val nextHighBit = n.hash and oldCapacity
                if (nextHighBit != highBit) {
                    if (broken == null) newTable[j or nextHighBit] = n else broken.next = n
                    broken = e
                    highBit = nextHighBit
                }
                e = n
                n = n.next
            }
            if (broken != null) broken.next = null
        }
        return newTable
    }

    /**
     * Subclass overrides this method to unlink entry.
     */
    fun postRemove(e: HashItem?) {}

    /**
     * Removes all mappings from this hash map, leaving it empty.
     *
     * @see .isEmpty
     *
     * @see .size
     */
    fun clear() {
        if (size != 0) {
            //Arrays.fill(table, null)
            table.fill(null)
            size = 0
        }
    }

    fun releaseItems(): K? {
        if (size == 0) return null
        var collisions = 0
        var max = 0
        var sum = 0
        var items: HashItem? = null
        var last: HashItem?
        var i = 0
        val n = table.size
        while (i < n) {
            val item = table[i]
            if (item == null) {
                i++
                continue
            }
            table[i] = null
            if (STATS) {
                sum = 0
                last = item
                while (last != null) {
                    if (last.next == null) break
                    sum++
                    last = last.next
                }
                max = max(max.toDouble(), sum.toDouble()).toInt()
                collisions += sum
            } else {
                last = last(item)
            }
            last!!.next = items
            items = item
            i++
        }
        if (STATS) println("collisions: $collisions $max $size")
        //Arrays.fill(table, null)
        table.fill(null)
        size = 0
        return items as K?
    }

    class HashItem : Inlist<HashItem>() {
        var hash = 0
        fun setIndex(hash: Int, next: HashItem?) {
            this.hash = hash
            this.next = next
        }
    }

    companion object {
        /**
         * Min capacity (other than zero) for a HashMap. Must be a power of two
         * greater than 1 (and less than 1 << 30).
         */
        private const val MINIMUM_CAPACITY = 4

        /**
         * Max capacity for a HashMap. Must be a power of two >= MINIMUM_CAPACITY.
         */
        private const val MAXIMUM_CAPACITY = 1 shl 30

        /**
         * An empty table shared by all zero-capacity maps (typically from default
         * constructor). It is never written to, and replaced on first put. Its size
         * is set to half the minimum, so that the first resize will create a
         * minimum-sized table.
         */
        private val EMPTY_TABLE = arrayOfNulls<HashItem>(MINIMUM_CAPACITY ushr 1)

        /**
         * The default load factor. Note that this implementation ignores the
         * load factor, but cannot do away with it entirely because it's
         * mentioned in the API.
         *
         *
         *
         * Note that this constant has no impact on the behavior of the program, but
         * it is emitted as part of the serialized form. The load factor of .75 is
         * hardwired into the program, which uses cheap shifts in place of expensive
         * division.
         */
        const val DEFAULT_LOAD_FACTOR = .75f

        /**
         * Returns an appropriate capacity for the specified initial size. Does
         * not round the result up to a power of two; the caller must do this!
         * The returned value will be between 0 and MAXIMUM_CAPACITY (inclusive).
         */
        fun capacityForInitSize(size: Int): Int {
            val result = (size shr 1) + size // Multiply by 3/2 to allow for growth

            // boolean expr is equivalent to result >= 0 && result<MAXIMUM_CAPACITY
            return if (result and (MAXIMUM_CAPACITY - 1).inv() == 0) result else MAXIMUM_CAPACITY
        }

        const val STATS = false

        /**
         * Applies a supplemental hash function to a given hashCode, which defends
         * against poor quality hash functions. This is critical because HashMap
         * uses power-of-two length hash tables, that otherwise encounter collisions
         * for hashCodes that do not differ in lower or upper bits.
         */
        private fun secondaryHash(h: Int): Int {
            // Doug Lea's supplemental hash function
            var h = h
            h = h xor (h ushr 20 xor (h ushr 12))
            return h xor (h ushr 7) xor (h ushr 4)
        }

        /**
         * Returns the smallest power of two >= its argument, with several caveats:
         * If the argument is negative but not Integer.MIN_VALUE, the method returns
         * zero. If the argument is > 2^30 or equal to Integer.MIN_VALUE, the method
         * returns Integer.MIN_VALUE. If the argument is zero, the method returns
         * zero.
         */
        private fun roundUpToPowerOfTwo(i: Int): Int {
            var i = i
            i-- // If input is a power of two, shift its high-order bit right

            // "Smear" the high-order bit all the way to the right
            i = i or (i ushr 1)
            i = i or (i ushr 2)
            i = i or (i ushr 4)
            i = i or (i ushr 8)
            i = i or (i ushr 16)
            return i + 1
        }


        //	public K put(K key) {
        //		//		if (key == null) {
        //		//			return putValueForNullKey(value);
        //		//		}
        //
        //		int hash = secondaryHash(key.hashCode());
        //		HashItem[] tab = table;
        //		int index = hash & (tab.length - 1);
        //		for (HashItem e = tab[index]; e != null; e = e.next) {
        //			if (e.hash == hash && key.equals(e.key)) {
        //				preModify(e);
        //				//V oldValue = e.value;
        //				//e.value = value;
        //				return e.key; //oldValue;
        //			}
        //		}
        //
        //		// No entry for (non-null) key is present; create one
        //		modCount++;
        //		if (size++ > threshold) {
        //			tab = doubleCapacity();
        //			index = hash & (tab.length - 1);
        //		}
        //		addNewEntry(key, hash, index);
        //		return null;
        //	}
        //	private V putValueForNullKey(V value) {
        //		HashMapEntry<K> entry = entryForNullKey;
        //		if (entry == null) {
        //			addNewEntryForNullKey(value);
        //			size++;
        //			modCount++;
        //			return null;
        //		} else {
        //			preModify(entry);
        //			V oldValue = entry.value;
        //			entry.value = value;
        //			return oldValue;
        //		}
        //	}
        //	/**
        //	 * Returns whether this map contains the specified key.
        //	 *
        //	 * @param key
        //	 *            the key to search for.
        //	 * @return {@code true} if this map contains the specified key,
        //	 *         {@code false} otherwise.
        //	 */
        //	//@Override
        //	public boolean containsKey(Object key) {
        //		if (key == null) {
        //			return entryForNullKey != null;
        //		}
        //
        //		// Doug Lea's supplemental secondaryHash function (inlined)
        //		int hash = key.hashCode();
        //		hash ^= (hash >>> 20) ^ (hash >>> 12);
        //		hash ^= (hash >>> 7) ^ (hash >>> 4);
        //
        //		HashItem[] tab = table;
        //		for (HashItem e = tab[hash & (tab.length - 1)]; e != null; e = e.next) {
        //			K eKey = e.key;
        //			if (eKey == key || (e.hash == hash && key.equals(eKey))) {
        //				return true;
        //			}
        //		}
        //		return false;
        //	}
        //	/**
        //	 * Returns whether this map contains the specified value.
        //	 *
        //	 * @param value
        //	 *            the value to search for.
        //	 * @return {@code true} if this map contains the specified value,
        //	 *         {@code false} otherwise.
        //	 */
        //	@Override
        //	public boolean containsValue(Object value) {
        //		HashMapEntry[] tab = table;
        //		int len = tab.length;
        //		if (value == null) {
        //			for (int i = 0; i < len; i++) {
        //				for (HashMapEntry e = tab[i]; e != null; e = e.next) {
        //					if (e.value == null) {
        //						return true;
        //					}
        //				}
        //			}
        //			return entryForNullKey != null && entryForNullKey.value == null;
        //		}
        //
        //		// value is non-null
        //		for (int i = 0; i < len; i++) {
        //			for (HashMapEntry e = tab[i]; e != null; e = e.next) {
        //				if (value.equals(e.value)) {
        //					return true;
        //				}
        //			}
        //		}
        //		return entryForNullKey != null && value.equals(entryForNullKey.value);
        //	}
        ///**
        // * Ensures that the hash table has sufficient capacity to store the
        // * specified number of mappings, with room to grow. If not, it increases the
        // * capacity as appropriate. Like doubleCapacity, this method moves existing
        // * entries to new buckets as appropriate. Unlike doubleCapacity, this method
        // * can grow the table by factors of 2^n for n > 1. Hopefully, a single call
        // * to this method will be faster than multiple calls to doubleCapacity.
        // *
        // * <p>
        // * This method is called only by putAll.
        // */
        //private void ensureCapacity(int numMappings) {
        //	int newCapacity = roundUpToPowerOfTwo(capacityForInitSize(numMappings));
        //	HashItem[] oldTable = table;
        //	int oldCapacity = oldTable.length;
        //	if (newCapacity <= oldCapacity) {
        //		return;
        //	}
        //	if (newCapacity == oldCapacity * 2) {
        //		doubleCapacity();
        //		return;
        //	}
        //
        //	// We're growing by at least 4x, rehash in the obvious way
        //	HashItem[] newTable = makeTable(newCapacity);
        //	if (size != 0) {
        //		int newMask = newCapacity - 1;
        //		for (int i = 0; i < oldCapacity; i++) {
        //			for (HashItem e = oldTable[i]; e != null;) {
        //				HashItem oldNext = e.next;
        //				int newIndex = e.hash & newMask;
        //				HashItem newNext = newTable[newIndex];
        //				newTable[newIndex] = e;
        //				e.next = newNext;
        //				e = oldNext;
        //			}
        //		}
        //	}
        //}
    }
}

